The paper presents an O^*(1.2312^n)-time and polynomial-space algorithm forthe traveling salesman problem in an n-vertex graph with maximum degree 3. Thisimproves the previous time bounds of O^*(1.251^n) by Iwama and Nakashima andO^*(1.260^n) by Eppstein. Our algorithm is a simple branch-and-searchalgorithm. The only branch rule is designed on a cut-circuit structure of agraph induced by unprocessed edges. To improve a time bound by a simpleanalysis on measure and conquer, we introduce an amortization scheme over thecut-circuit structure by defining the measure of an instance to be the sum ofnot only weights of vertices but also weights of connected components of theinduced graph.
展开▼
